iT邦幫忙

2021 iThome 鐵人賽

DAY 18
0
自我挑戰組

JAVA的實作與應用系列 第 18

Day 18 Sort

  • 分享至 

  • xImage
  •  

演算法在程式設計中扮演重要的角色,而演算法和時間複雜度有很大的關聯,
時間複雜度本意為程式執行的時間,寫出好的演算法就會有好的時間複雜度,
程式就會執行的有效率 ; 此外還有空間複雜度,指演算法在計算機內執行時所需的儲存空間。
今天要介紹三個基本的演算法:氣泡排序、選擇排序、插入排序。

1 氣泡排序:是指對n個數進行排序,每次都是由前一個數跟後一個數比較, 每執行一輪迴圈,就可以將最小的數排到最上面,迴圈n-1輪,即可完成排序,程式執行如下:
https://ithelp.ithome.com.tw/upload/images/20210930/20140456AEuPH9eV15.png
使用swap方法將陣列裡的資料一一比對,執行完迴圈陣列由小到大排好。

2 選擇排序:在每一次迴圈內都由一個數去跟所有的數都比較一次,每次執行程式都挑出較小的數字出來進行比較,再通過一次交換將最小的數放在最前面,通過n-1次迴圈之後完成排序。對於氣泡排序來說,比較的次數並沒有改變,但是資料交換的次數比氣泡排序少很多,程式執行如下:
https://ithelp.ithome.com.tw/upload/images/20210930/20140456csofjePIcM.png

i控制迴圈次數,從零開始,並且要小於陣列的長度,j控制迴圈次數,從一開始,因為要和前一個數比,所以不能從零開始,才不會重疊比較,最後if條件式,後面一個數比前面小的話,則交換,把大的數往後放。

3 插入排序:首先先預設陣列的第一個數是已經排序過的,接著從陣列裡面
然後取下一個數,與已經排序的數按從後向前的順序依次比較,如果該數比當前位置排好序的數小,則將排好序的數的位置向後移一位,直到排序完成,程式碼如下:
https://ithelp.ithome.com.tw/upload/images/20210930/20140456GfoREku2F4.png


上一篇
Day 17 Swap
下一篇
Day 19 Method
系列文
JAVA的實作與應用30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言